Autostrady
Limit pamięci: 32 MB
Bajtocja leży na półwyspie.
Już od czasów króla Bitola podstawową formą komunikacji w Bajtocji
jest transport kolejowy.
Król Bitol wybudował jedną super szybką linię kolejową łączącą
wschodnie i zachodnie wybrzeże półwyspu.
Linia kolejowa przechodzi przez wszystkie miasta Bajtocji, wyznaczając
ich numerację - pierwsze miasto na linii ma numer 1, a ostatnie .
Miasto nr 1 leży na zachodnim, a nr na wschodnim wybrzeżu.
W ostatnich latach, dzięki ministrowi Bajterowiczowi,
gospodarka Bajtocji rozwinęła się bardzo gwałtownie i obecna sieć
komunikacyjna wymaga szybkiej modernizacji.
Król Bajtol zarządził (w ramach kolejnego planu -letniego)
budowę wielu autostrad.
Każda z autostrad ma łączyć bezpośrednio dwa wybrane miasta Bajtocji.
Ze względu na to, że każda autostrada będzie budowana przez
oddzielną agencję rządową i na każdej będzie obowiązywał inny rodzaj
winiet, zdecydowano, że
autostrady nie mogą przecinać się same ze sobą, ani też nie mogą przecinać
linii kolejowej.
Stąd jedyną możliwością jest zbudowanie autostrad po północnej lub
południowej stronie linii kolejowej.
Na rysunku 2 przedstawiono przykładowy plan autostrad
(autostrady są zaznaczone łukami, a linia kolejowa to łamana składająca
się z odcinków).
Najjaśniejszy król Bajtol zdecydował już jakie pary miast mają
zostać połączone autostradami.
Każda z autostrad opisana jest przez parę miast, które ma łączyć.
Twoim zadaniem jest ustalenie dla danego zestawu połączeń,
które z autostrad powinny leżeć na północ od linii kolejowej,
a które na południe.
Pamiętaj jednak że autostrady nie mogą się wzajemnie przecinać,
ani też przecinać linii kolejowej.
Zadanie
Napisz program, który:
-
wczyta ze standardowego wejścia informację o planowanych
autostradach,
-
wyznaczy rozmieszczenie autostrad
(lub stwierdzi, że nie da się ich zbudować),
-
zapisze wynik na standardowym wyjściu.
Wejście
W pierwszym wierszu standardowego wejścia zapisane są dwie
liczby całkowite - liczba miast i
liczba planowanych autostrad ,
.
W kolejnych wierszach zapisane są pary miast, które mają
zostać połączone autostradami.
W wierszu zapisane są dwie liczby całkowite
, oddzielone
pojedynczym odstępem - numery miast, które ma połączyć
-ta autostrada, .
Pary miast w danych wejściowych nie powtarzają się.
Wyjście
Twój program powinien wypisać na standardowe wyjście plan budowy
autostrad, lub pojedyncze słowo NIE, jeśli nie jest
możliwe zbudowanie wszystkich autostrad.
Jeśli budowa autostrad jest możliwa, to na standardowe
wyjście należy wypisać wierszy.
W -tym wierszu należy wypisać jedną wielką literę,
odpowiednio N - jeśli autostrada łącząca miasta
i ma zostać
zbudowana na północ od linii kolejowej,
lub S - jeśli na południe od linii kolejowej.
Jeśli istnieje wiele możliwych rozwiązań, Twój program powinien
wypisać tylko jedno z nich.
Przykład
Dla danych wejściowych:
8 7
1 2
1 3
2 4
5 7
4 8
7 8
6 8
poprawną odpowiedzią jest:
N
N
S
S
S
N
N
Autor zadania: Tomasz Waleń.